import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MyBinaryTree {

        static class TreeNode {
            public int val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用

            public TreeNode(int val) {
                this.val = val;
            }
        }


        /**
         * 创建一棵二叉树 返回这棵树的根节点
         *
         * @return
         */
        public TreeNode createTree() {
                TreeNode root = new TreeNode(1);
                root.left = new TreeNode(2);
                root.right = new TreeNode(3);
                root.left.left = new TreeNode(4);
                root.left.right = new TreeNode(5);
                return root;
        }

        // 前序遍历
        public void preOrder(TreeNode root) {
                if(root == null) return;
                System.out.print(root.val + " ");
                preOrder(root.left);
                postOrder(root.right);
        }

        // 中序遍历
        void inOrder(TreeNode root) {
                if(root == null) return;
                preOrder(root.left);
                System.out.print(root.val + " ");
                postOrder(root.right);
        }

        // 后序遍历
        void postOrder(TreeNode root) {
                if(root == null) return;
                preOrder(root.left);
                postOrder(root.right);
                System.out.print(root.val + " ");
        }

        public int nodeSize;

        /**
         * 获取树中节点的个数：遍历思路
         */
        void size(TreeNode root) {
                if(root == null) return;
                size(root.left);
                size(root.right);
                nodeSize++;
        }

        /**
         * 获取节点的个数：子问题的思路
         *
         * @param root
         * @return
         */
        int size2(TreeNode root) {
                if(root == null) return 0;
                return size2(root.left) + size2(root.right) + 1;
        }


        /*
         获取叶子节点的个数：遍历思路
         */
        public static int leafSize = 0;

        void getLeafNodeCount1(TreeNode root) {
                if(root == null) return;
                if(root.left == null && root.right == null){
                        leafSize++;
                }
                getLeafNodeCount1(root.left);
                getLeafNodeCount1(root.right);
        }

        /*
         获取叶子节点的个数：子问题
         */
        int getLeafNodeCount2(TreeNode root) {
                if(root == null) return 0;
                if(root.left == null && root.right == null){
                        return 1;
                }
                return getLeafNodeCount2(root.left)+ getLeafNodeCount2(root.right);
        }

        /*
        获取第K层节点的个数
         */
        int getKLevelNodeCount(TreeNode root, int k) {
                if(root == null) return 0;
                if(k == 1) return 1;
                return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
        }

        /*
         获取二叉树的高度
         时间复杂度：O(N)
         */
        int getHeight(TreeNode root) {
                if(root == null) return 0;
                int leftHeight = getHeight(root.left);
                int rightHeight = getHeight(root.right);
                return Math.max(getHeight(root.left) + 1,getHeight(root.right) + 1);
        }


        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, char val) {
                if(root == null) return null;
                if(root.val == val) return root;

                TreeNode node = find(root.left,val);
                if(node != null) {
                        return node;
                }
                return find(root.right, val);
        }

        //层序遍历
        void levelOrder(TreeNode root) {
                class Solution {
                        public List<List<Integer>> levelOrder(TreeNode root) {
                                List<List<Integer>> list = new LinkedList<>();
                                if(root == null) {
                                        return list;
                                }
                                Queue<TreeNode> queue = new LinkedList<>();
                                TreeNode cur = root;
                                queue.offer(cur);
                                while(!queue.isEmpty()) {
                                        int size = queue.size();
                                        List<Integer> newlist = new LinkedList<>();
                                        while(size != 0) {
                                                TreeNode top = queue.poll();
                                                if(top.left != null) {
                                                        queue.offer(top.left);
                                                }
                                                if(top.right != null) {
                                                        queue.offer(top.right);
                                                }
                                                newlist.add(top.val);
                                                size--;
                                        }
                                        list.add(newlist);
                                }
                                return list;
                        }
                }
        }


        // 判断一棵树是不是完全二叉树
        public boolean isCompleteTree(TreeNode root) {
                if(root == null) {
                        return true;
                }
                Queue<TreeNode> queue = new LinkedList<>();
                TreeNode cur = root;
                queue.offer(cur);
            while(!queue.isEmpty()) {
                            cur = queue.poll();
                            if (cur == null) {
                                    break;
                            }
                            queue.offer(cur.left);
                            queue.offer(cur.right);
            }
            while(!queue.isEmpty()) {
                    TreeNode top = queue.poll();
                    if(top != null) {
                            return false;
                    }
            }
            return true;
        }
}
